package lib

//link to 370
func init() {
	Probs = append(Probs, Problem{
		Num:         1094,
		Discription: "每段路程有一些乘客数量，车的容量能不能运送完所有乘客",
		Level:       2,
		Labels: map[string]int{
			"差分数组": 1,
			"前缀和":  1,
		},
	})
}

//差分数组的思想：将连续范围内的修改优化成 2 * O（1）
//diff[i]=res[i]-res[i-1],diff[0]=res[0]
//res[i]=diff[0]+diff[1]+..diff[i]
func CarPooling(trips [][]int, capacity int) bool {
	maxTo := 0
	for i := range trips {
		maxTo = max(maxTo, trips[i][2])
	}

	diff := make([]int, maxTo+1)
	for i := range trips {
		diff[trips[i][1]] += trips[i][0]
		//先减去下车，后加上上车，所以在终点站处就可以减了
		diff[trips[i][2]] -= trips[i][0]
	}

	//每公里处车内的人数
	count := 0
	for i := range diff {
		count += diff[i]
		if count > capacity {
			return false
		}
	}

	return true
}
